package DP_354;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


public class Solution {
	public int maxEnvelopes(int[][] envelopes) {
		int n = envelopes.length;
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] a, int[] b) {
				return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
			}
		});

		int[] hight = new int[n];
		for (int i = 0; i < envelopes.length; i++) {
			hight[i] = envelopes[i][1];
		}
		return LIS(hight);
	}

	private int LIS(int[] hight) {
		int[] dp = new int[hight.length];
		Arrays.fill(dp, 1);
		for (int i = 1; i < hight.length; i++) {
			for (int j = 0; j < i; j++) {
				if (hight[i]>hight[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < dp.length; i++) {
			ans = Math.max(dp[i], ans);
		}

		return ans;
	}
}
